﻿using System;

public class SingleLinkedList<T> : IListDS<T>
{
    private Node<T> head;//单链表头引用
    public Node<T> Head { get { return head; } set { head = value; } }

    public SingleLinkedList()
    {
        head = null;
    }

    // 在链表的尾部添加新元素
    public void Append(T item)
    {
        Node<T> q = new Node<T>(item);
        Node<T> p = new Node<T>();
        if (head == null)
        {
            head = q;
            return;
        }

        p = head;
        while (p.Next != null)
        {
            p = p.Next;
        }
        p.Next = q;
    }

    // 头插法
    public void AppendHead(T item)
    {
        Node<T> q = new Node<T>(item);
        Node<T> p = new Node<T>();
        if (head == null)
        {
            head = q;
            return;
        }
        p = head;
        head = q;
        q.Next = p;
    }

    public void Clear()
    {
        head = null;
    }

    // s删除单链表的第i个结点
    public T Delete(int i)
    {
        if (IsEmpty() || i < 0)
        {
            Console.WriteLine("Link is empty or Position is error!");
            return default(T);
        }

        Node<T> q = new Node<T>();
        if (i == 1)
        {
            q = head;
            head = head.Next;
            return q.Data;
        }

        Node<T> p = head;
        int j = 1;
        while (p.Next != null && j < i)
        {
            ++j;
            q = p;
            p = p.Next;
        }

        if (j == i)
        {
            q.Next = p.Next;
            return p.Data;
        }
        else
        {
            Console.WriteLine("The ith node is not exist!");
            return default(T);
        }
    }

    public T GetElem(int i)
    {
        if (IsEmpty())
        {
            Console.WriteLine("List is empty!");
            return default(T);
        }

        Node<T> p = new Node<T>();
        p = head;
        int j = 1;
        while (p.Next != null && j < i)
        {
            ++j;
            p = p.Next;
        }

        if (j == i)
        {
            return p.Data;
        }
        else
        {
            Console.WriteLine("The ith node is not exist!");
            return default(T);
        }
    }

    // 求单链表的长度
    public int GetLength()
    {
        Node<T> p = head;
        int len = 0;
        while (p != null)
        {
            ++len;
            p = p.Next;
        }
        return len;
    }

    // 在单链表的第i个结点位置前插入一个值为item的结点
    public void Insert(T item, int i)
    {
        if (IsEmpty() || i < 1)
        {
            Console.WriteLine("List is empty or Position is error");
            return;
        }

        if (i == 1)
        {
            Node<T> q = new Node<T>(item);
            q.Next = head;
            head = q;
            return;
        }

        Node<T> p = head;
        Node<T> r = new Node<T>();
        int j = 1;
        while (p.Next != null && j < i)
        {
            r = p;
            p = p.Next;
            ++j;
        }

        if (j == i)
        {
            Node<T> q = new Node<T>(item);
            q.Next = p;
            r.Next = q;
        }
    }

    // 在单链表第i个结点后插入值为item的结点
    public void InsertPost(T item, int i)
    {
        if (IsEmpty() || i < 1)
        {
            Console.WriteLine("List is empty or Position is error");
            return;
        }

        if (i == 1)
        {
            Node<T> q = new Node<T>(item);
            q.Next = head.Next;
            head.Next = q;
            return;
        }

        Node<T> p = head;
        int j = 1;
        while (p != null && j < i)
        {
            p = p.Next;
            ++j;
        }

        if (j == i)
        {
            Node<T> q = new Node<T>(item);
            q.Next = p.Next;
            p.Next = q;
        }
    }

    public bool IsEmpty()
    {
        if (head == null)
        {
            return true;
        }
        else
        {
            return false;
        }
    }

    public int Locate(T value)
    {
        if (IsEmpty())
        {
            Console.WriteLine("List is Empty!");
            return -1;
        }

        Node<T> p = new Node<T>();
        p = head;
        int i = 1;
        while (!p.Data.Equals(value) && p.Next != null)
        {
            p = p.Next;
            ++i;
        }
        return i;
    }

    public void Reverse()
    {
        Node<T> p = head;
        Node<T> q = new Node<T>();
        Node<T> tmp = null;
        while (p != null)
        {
            q = p;
            p = p.Next;
            q.Next = tmp;
            tmp = q;
        }
        head = q;
    }

    public Node<T> Reverse(Node<T> target)
    {
        Node<T> p = head;
        Node<T> q = new Node<T>();
        Node<T> tmp = null;
        while (p != target)
        {
            q = p;
            p = p.Next;
            q.Next = tmp;
            tmp = q;
        }
        head = q;
        return q;
    }
}
